package code;

import java.util.Arrays;

public class Code87 {
	
	/*
	 * dp[k][i][j]表示状态
	 * k表示长度
	 * i表示s1的起点
	 * j表示s2的起点
	 * dp[k][i][j]=true,表示s1[i~i+k]是可以转化成s2[j~j+k]
	 * 否则，不行
	 * 状态转移方程
	 * 
	 * 0<m<k
	 * dp[k][i][j]={(dp[m][i][j] && dp[k-m][i+m][j+m]) || 
	 * (dp[m][i][j+k-m] && dp[k-m][i+k][j])}
	 * 举例说明转移
	 * s1=a1+b1(划分成两段)
	 * s2=a2+b2(同理)
	 * s2=a3+b3
	 * (1)
	 * 	a1~a2
	 * 	b1~b2
	 * (2)
	 * 	a1~b3
	 *  b1~a3
	 */
    public boolean isScramble(String s1, String s2) {
    	int n=s1.length();
    	int i,j,k,m;
    	if(n!=s2.length())
    		return false;
    	if(s1.equals(s2))
    		return true;
    	char[] C1=s1.toCharArray();
    	char[] C2=s2.toCharArray();
    	Arrays.sort(C1);
    	Arrays.sort(C2);
    	for(i=0;i<n;i++){
    		if(C1[i]!=C2[i])
    			return false;
    	}
    	
    	boolean[][][] dp=new boolean[n][n][n];
    	
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++){
    			if(s1.charAt(i)==s2.charAt(j))
    				dp[0][i][j]=true;
    		}
    	
    	for(k=2;k<=n;k++)
    		for(i=0;i<=n-k;i++)
    			for(j=0;j<=n-k;j++){
    				boolean record=false;
    				for(m=1;m<k && !record;m++){
    					record=(dp[m-1][i][j] && dp[k-1-m][i+m][j+m]) ||
    							(dp[m-1][i][j+k-m] && dp[k-1-m][i+m][j]);
    				}
    				dp[k-1][i][j]=record;
    			}
        return dp[n-1][0][0];
    }
    
    public static void main(String[] args){
    	String s1="ab";
    	String s2="ba";
    	System.out.println(new Code87().isScramble(s1, s2));
    }
}
